#include <DM_Soundex.h>
#include <stdafx.h>

// CompareNGram function compares an n-gram to a a substring of the name, at the start 
// position specified in the name string.  Result is LT(-1), EQ(0) or GT(1).
int DM_Soundex::CompareNGram(int startpos, BYTE *ngram, BYTE *name, int length) {
	// Uses memcmp to compare an name n-gram to a rule n-gram
	int result = EQ;
	int i = memcmp(name + startpos, ngram, length);
	if (i < EQ)
		result = LT;
	else if (i > EQ)
		result = GT;
	return (result);
}

// This function cleans a string up in-place, removing all punctuation/non-alphabetic 
// chars and capitalizing the rest.  It updates the length when done (in case non-usable
// characters were removed)
void DM_Soundex::CleanString(BYTE *name, int &length) {
	int readpos = 0;
	int writepos = 0;
	while (readpos < length) {
		BYTE c = *(name + readpos);
        if (c >= 'a' && c <= 'z')
			c = c - 'a' + 'A';
		if (c >= 'A' && c <= 'Z') {
			*(name + writepos++) = c;
		}
		readpos++;
	}
	// Set the new length to the current write position
	length = writepos;
	// Set any remaining characters to '\0'
	while (writepos < readpos)
		*(name + writepos++) = '\0';
}

// Enqueue a rule in the RuleQueue
void RuleQueue::EnQueue(DM_Rule *rule) {
	// If there's room in the queue, we add the new rule and increment the write
	// pointer
	if (write < QUEUE_MAX_LENGTH) 
		QueueArray[write++] = *rule;
}

// Dequeue a rule from the RuleQueue
DM_Rule RuleQueue::DeQueue() {
	// If we have an item left, we return it and increment the read counter
	if (this->ItemsLeft()) {
		return (QueueArray[read++]);
	} else {
		// Otherwise we return an un-initialized rule
		DM_Rule d;
		return d;
	}
}	

// Are there any items left in the RuleQueue?
bool RuleQueue::ItemsLeft() {
	// If read < write, we have items left in the queue
	return (read < write);
}

// Checks the beginning of the name for an n-gram that fits the beginning of
// name rules
DM_Rule DM_Soundex::CheckBeginning(BYTE *name, int &start, int finish) {
	int nGramLength = DM_RULE_BEGINNING_LAST_SET;
	DM_Rule MatchRule;
	bool FoundMatch = false;
	while (nGramLength >= 0 && !FoundMatch) {
		if (finish > nGramLength) {
			// Here we perform a binary search to locate matching rules
			bool Done = false;
			int left = DM_Rule_Beginning_Bounds[nGramLength].Lower;
			int right = DM_Rule_Beginning_Bounds[nGramLength].Upper;
			int mid = (left + right) / 2;
			while (!Done) {
				int j = CompareNGram(0, (DM_Rule_Beginning + mid)->nGram, name, nGramLength + 1);
				if (j == 0) {
					MatchRule = DM_Rule_Beginning[mid];
					Done = true;
					FoundMatch = true;
				} else if (j == LT) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
				mid = (left + right) / 2;
				if (left > right)
					Done = true;
			}
		}
		nGramLength--;
	}
	if (FoundMatch) {
		start += MatchRule.nGramLength;
	}
	return MatchRule;
}

// Checks anywhere in the name for an n-gram that fits the anywhere in name
// rules
DM_Rule DM_Soundex::CheckAnywhere(BYTE *name, int &start, int &finish) {
	int nGramLength = DM_RULE_ANYWHERE_LAST_SET;
	DM_Rule MatchRule;
	bool FoundMatch = false;
	while (nGramLength >= 0 && !FoundMatch) {
		if (finish - start + 1 > nGramLength) {
			// Here we perform a binary search to locate a matching rule
			bool Done = false;
			int left = DM_Rule_Anywhere_Bounds[nGramLength].Lower;
			int right = DM_Rule_Anywhere_Bounds[nGramLength].Upper;
			int mid = (left + right) / 2;
			while (!Done) {
				int j = CompareNGram(start, (DM_Rule_Anywhere + mid)->nGram, name, nGramLength + 1);
				if (j == 0) {
					MatchRule = DM_Rule_Anywhere[mid];
					Done = true;
					FoundMatch = true;
				} else if (j == LT) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
				mid = (left + right) / 2;
				if (left > right)
					Done = true;
			}
		}
		nGramLength--;
	}
	if (FoundMatch) {
		start += MatchRule.nGramLength;
	}
	return MatchRule;
}

// Checks the ending of the name for an n-gram that fits the ending of name
// rules
DM_Rule DM_Soundex::CheckEnding(BYTE *name, int &start, int &finish) {
	int nGramLength = DM_RULE_ENDING_LAST_SET;
	DM_Rule MatchRule;
	bool FoundMatch = false;
	while (nGramLength >= 0 && !FoundMatch) {
		if (finish - start + 1 > nGramLength) {
			bool Done = false;
			// For this one, we perform a binary search to locate a matching rule
			int left = DM_Rule_Ending_Bounds[nGramLength].Lower;
			int right = DM_Rule_Ending_Bounds[nGramLength].Upper;
			int mid = (left + right) / 2;
			while (!Done) {
				int j = CompareNGram(finish - nGramLength, (DM_Rule_Ending + mid)->nGram, name, nGramLength + 1);
				if (j == 0) {
					MatchRule = DM_Rule_Ending[mid];
					Done = true;
					FoundMatch = true;
				} else if (j == LT) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
				mid = (left + right) / 2;
				if (left > right)
					Done = true;
			}
		}
		nGramLength--;
	}
	if (FoundMatch) {
		finish -= MatchRule.nGramLength;
	}
	return MatchRule;
}

// Enqueues all of the rules necessary to encode a name 
void DM_Soundex::QueueRules(BYTE *name, int &length, RuleQueue &q) {
	DM_Rule r;
	// Start by cleaning the name of all punctuation and capitalizing it
	DM_Soundex::CleanString(name, length);
	// Set the start and finish parameters
	int start = 0;
	int finish = length - 1;
	// If we have at least one character to encode...
	if (finish > -1) {
		// Start by grabbing a beginning of name match
		DM_Rule beginmatch;
		beginmatch = DM_Soundex::CheckBeginning(name, start, finish);
		// A Code of 255 indicates that this rule has been initialized, but not yet
		// populated; i.e., no result from CheckBeginning routine
		if (beginmatch.Code1 != 255) {
			// If we have a begin match, enqueue it
			q.EnQueue(&beginmatch);
		}
		// Now we check for an ending match
		DM_Rule endmatch;
		// We save the result for later.  We perform it now so that the start and finish
		// variables are properly set to include only the inner portion of the name
		endmatch = DM_Soundex::CheckEnding(name, start, finish);
		// Now we loop through all the n-grams inside the name
		while (start <= finish) {
			// We perform an anywhere match on the n-grams in this loop
			DM_Rule anymatch;
			anymatch = DM_Soundex::CheckAnywhere(name, start, finish);
			// If we have a match, enqueue it
			if (anymatch.Code1 != 255) {
				q.EnQueue(&anymatch);
			}
		}
		// Last step, if we have an end match, enqueue it as well
		if (endmatch.Code1 != 255) {
			q.EnQueue(&endmatch);
		}
	}
}

// This routine initializes our encodings
void DM_Soundex::InitEncodings() {
	// Set all encodings (up to 64 * 8 bytes each) to ASCII '0' char
	memset(DM_Encodings, '0', 512 * sizeof(BYTE));
	// Every 7th and 8th byte set to '\0'
	for (int i = 0; i < 64; i++) {
		DM_Encodings[i * 8 + 6] = 0;
		DM_Encodings[i * 8 + 7] = 0;
	}
}

// This function splits our encodings (doubles them) up to 64
void DM_Soundex::SplitEncodings(int &count) {
	// If we have less than 64 total encodings, we can duplicate/copy all encodings
	// to the back-end and double the encoding count
	if (count < 64) {
		memcpy(DM_Encodings + count * 8, DM_Encodings, count * 8);
		count *= 2;
	}
}

// This function appends a code to the end of our encoding
void DM_Soundex::AppendCode(BYTE *encoding, BYTE length, BYTE code) {
	// Start our 'last code' with an obviously invalid character
	BYTE lastcode = '*';
	// If the encoding length is > 0, we grab the previous character as our last code
	if (length > 0)
		lastcode = *(encoding + length - 1);
	// Overwrite zeroes (other than the very first one)
	if (code < 10) { // Single digit code
		// Turn it into an ASCII printable digit
		code += '0';
		// If we encounter a zero after the first character, or if we have a duplicate
		// code, we go back one character
		if ((lastcode == '0' && length > 1) || lastcode == code)
			length--;
		if (length < 6) {  // Only go up to 6 character encodings
			// Set the current character to the code and increment the length
			*(encoding + length) = code;
			*(encoding + 7) = ++length;
		}
	} else if (code < 100) { // Double-digit code
		// Split the code into two separate digits and make them ASCII printable
		BYTE c1 = (code / 10) + '0';
		BYTE c2 = (code % 10) + '0';
		// If the last character is a '0' and we are beyond the first character, or if
		// the last character is the same as the first character of the new code,
		// go back one character
		if ((lastcode == '0' && length > 1) || lastcode == c1)
			length--;
        if (length < 6) { // Only go up to 6 character encodings
			// Here we set the first character of the encoding and increment the length
			// by one
			*(encoding + length) = c1;
			*(encoding + 7) = ++length;
			// If we are still less than 6 characters in length, we can add the second
			// half of the code and increment the length by 1
			if (length < 6) {
				*(encoding + length) = c2;
				*(encoding + 7) = ++length;
			}
		}
	}
}

// Applies all rules in the queue to generate D-M codes
int DM_Soundex::ApplyRules(RuleQueue &q) {
	DM_Rule r;
	// We start with 1 encoding
	int EncodingCount = 1;
	// Loop until we run out of rules in the queue
	while (q.ItemsLeft()) {
		// Grab the next rule from the queue
		r = q.DeQueue();
		// If our Code1 and Code2 do not match, we split/double the number of
		// encodings
		if (r.Code1 != r.Code2) {
			SplitEncodings(EncodingCount);
		}
		// Find the half-way point
		int j = (EncodingCount / 2) - 1;
		// Loop through the back half, applying one code
		for (int i = j + 1; i <= EncodingCount - 1; i++) {
			AppendCode(DM_Encodings + i * 8, DM_Encodings[i * 8 + 7], r.Code1);
		}
		// Loop through the front half, applying the other code
		for (int i = 0; i <= j; i++) {
			AppendCode(DM_Encodings + i * 8, DM_Encodings[i * 8 + 7], r.Code2);
		}
	}
	// Return the number of encodings
	return EncodingCount;
}

// This routine marks all duplicates to eliminate them
void DM_Soundex::MarkDupes(int count) {
	// Loop through and mark all duplicates.  This is an O(N^2) Order routine because of
	// the double loop
	for (int i = 0; i < count; i++) {
		// Keep track of the total encodings that match the current one
		int total = 0;
		// Double-loop
		for (int j = 0; j < count; j++) {
			// If the outer encoding matches the inner encoding, we add 1 to the total
			if (DM_Soundex::CompareNGram(0, DM_Encodings + i * 8, DM_Encodings + j * 8, 6) == EQ)
				total++;
		}
		// If our total is more than 1, we have a dupe, so mark it by placing a \0 in
		// the first position
		if (total > 1) {
			*(DM_Encodings + i * 8) = '\0';
		}
	}
}

// The main function.  This function 
int DM_Soundex::Encode(BYTE *name, int &length) {
	// Create a rule queue
	RuleQueue q;
	// Clean up the name and enqueue all of the encoding rules
	this->QueueRules(name, length, q);
	// Initialize our Encodings Table
	this->InitEncodings();
	// Apply all the rules and return the Count of Encodings
	int EncodingCount = this->ApplyRules(q);
	// Mark all duplicates
	this->MarkDupes(EncodingCount);
	// Return the number of encodings
	return EncodingCount;
}

// === Rule Sets ===

// Anywhere Rules
DM_Rule_Bounds DM_Soundex::DM_Rule_Anywhere_Bounds[5] = {
	DM_Rule_Bounds (0, 25),
	DM_Rule_Bounds (26, 74),
	DM_Rule_Bounds (75, 164),
	DM_Rule_Bounds (165, 168),
	DM_Rule_Bounds (169, 169)
};

DM_Rule DM_Soundex::DM_Rule_Anywhere[170] = {
	DM_Rule (0, 1, "A", 0),
	DM_Rule (1, 1, "B", 7),
	DM_Rule (2, 1, "C", 5, 4),
	DM_Rule (3, 1, "D", 3),
	DM_Rule (4, 1, "E", 0),
	DM_Rule (5, 1, "F", 7),
	DM_Rule (6, 1, "G", 5),
	DM_Rule (7, 1, "H", 0),
	DM_Rule (8, 1, "I", 0),
	DM_Rule (9, 1, "J", 1, 4),
	DM_Rule (10, 1, "K", 5),
	DM_Rule (11, 1, "L", 8),
	DM_Rule (12, 1, "M", 6),
	DM_Rule (13, 1, "N", 6),
	DM_Rule (14, 1, "O", 0),
	DM_Rule (15, 1, "P", 7),
	DM_Rule (16, 1, "Q", 5),
	DM_Rule (17, 1, "R", 9),
	DM_Rule (18, 1, "S", 4),
	DM_Rule (19, 1, "T", 3),
	DM_Rule (20, 1, "U", 0),
	DM_Rule (21, 1, "V", 7),
	DM_Rule (22, 1, "W", 7),
	DM_Rule (23, 1, "X", 54),
	DM_Rule (24, 1, "Y", 0),
	DM_Rule (25, 1, "Z", 4),
	DM_Rule (26, 2, "AI", 0),
	DM_Rule (27, 2, "AJ", 0),
	DM_Rule (28, 2, "AU", 0),
	DM_Rule (29, 2, "AY", 0),
	DM_Rule (30, 2, "CH", 5, 4),
	DM_Rule (31, 2, "CK", 5, 45),
	DM_Rule (32, 2, "CS", 4),
	DM_Rule (33, 2, "CZ", 4),
	DM_Rule (34, 2, "DS", 4),
	DM_Rule (35, 2, "DT", 3),
	DM_Rule (36, 2, "DZ", 4),
	DM_Rule (37, 2, "EI", 0),
	DM_Rule (38, 2, "EJ", 0),
	DM_Rule (39, 2, "EU", 0),
	DM_Rule (40, 2, "EY", 0),
	DM_Rule (41, 2, "FB", 7),
	DM_Rule (42, 2, "HA", 5),
	DM_Rule (43, 2, "HE", 5),
	DM_Rule (44, 2, "HI", 5),
	DM_Rule (45, 2, "HO", 5),
	DM_Rule (46, 2, "HU", 5),
	DM_Rule (47, 2, "HY", 5),
	DM_Rule (48, 2, "IA", 0),
	DM_Rule (49, 2, "IE", 0),
	DM_Rule (50, 2, "IO", 0),
	DM_Rule (51, 2, "IU", 0),
	DM_Rule (52, 2, "KH", 5),
	DM_Rule (53, 2, "MN", 66),
	DM_Rule (54, 2, "NM", 66),
	DM_Rule (55, 2, "OI", 0),
	DM_Rule (56, 2, "OJ", 0),
	DM_Rule (57, 2, "OY", 0),
	DM_Rule (58, 2, "PF", 7),
	DM_Rule (59, 2, "PH", 7),
	DM_Rule (60, 2, "RS", 94, 4),
	DM_Rule (61, 2, "RZ", 94, 4),
	DM_Rule (62, 2, "SH", 4),
	DM_Rule (63, 2, "ST", 43),
	DM_Rule (64, 2, "SZ", 4),
	DM_Rule (65, 2, "TC", 4),
	DM_Rule (66, 2, "TH", 3),
	DM_Rule (67, 2, "TS", 4),
	DM_Rule (68, 2, "TZ", 4),
	DM_Rule (69, 2, "UE", 0),
	DM_Rule (70, 2, "UI", 0),
	DM_Rule (71, 2, "UJ", 0),
	DM_Rule (72, 2, "UY", 0),
	DM_Rule (73, 2, "ZH", 4),
	DM_Rule (74, 2, "ZS", 4),
	DM_Rule (75, 3, "AIA", 1),
	DM_Rule (76, 3, "AIE", 1),
	DM_Rule (77, 3, "AII", 1),
	DM_Rule (78, 3, "AIO", 1),
	DM_Rule (79, 3, "AIU", 1),
	DM_Rule (80, 3, "AIY", 1),
	DM_Rule (81, 3, "AJA", 1),
	DM_Rule (82, 3, "AJE", 1),
	DM_Rule (83, 3, "AJI", 1),
	DM_Rule (84, 3, "AJO", 1),
	DM_Rule (85, 3, "AJU", 1),
	DM_Rule (86, 3, "AJY", 1),
	DM_Rule (87, 3, "AUA", 1),
	DM_Rule (88, 3, "AUE", 1),
	DM_Rule (89, 3, "AUI", 1),
	DM_Rule (90, 3, "AUO", 1),
	DM_Rule (91, 3, "AUU", 1),
	DM_Rule (92, 3, "AUY", 1),
	DM_Rule (93, 3, "AYA", 1),
	DM_Rule (94, 3, "AYE", 1),
	DM_Rule (95, 3, "AYI", 1),
	DM_Rule (96, 3, "AYO", 1),
	DM_Rule (97, 3, "AYU", 1),
	DM_Rule (98, 3, "AYY", 1),
	DM_Rule (99, 3, "CSZ", 4),
	DM_Rule (100, 3, "CZS", 4),
	DM_Rule (101, 3, "DRS", 4),
	DM_Rule (102, 3, "DRZ", 4),
	DM_Rule (103, 3, "DSH", 4),
	DM_Rule (104, 3, "DSZ", 4),
	DM_Rule (105, 3, "DZH", 4),
	DM_Rule (106, 3, "DZS", 4),
	DM_Rule (107, 3, "EIA", 1),
	DM_Rule (108, 3, "EIE", 1),
	DM_Rule (109, 3, "EII", 1),
	DM_Rule (110, 3, "EIO", 1),
	DM_Rule (111, 3, "EIU", 1),
	DM_Rule (112, 3, "EIY", 1),
	DM_Rule (113, 3, "EJA", 1),
	DM_Rule (114, 3, "EJE", 1),
	DM_Rule (115, 3, "EJI", 1),
	DM_Rule (116, 3, "EJO", 1),
	DM_Rule (117, 3, "EJU", 1),
	DM_Rule (118, 3, "EJY", 1),
	DM_Rule (119, 3, "EUA", 1),
	DM_Rule (120, 3, "EUE", 1),
	DM_Rule (121, 3, "EUI", 1),
	DM_Rule (122, 3, "EUO", 1),
	DM_Rule (123, 3, "EUU", 1),
	DM_Rule (124, 3, "EUY", 1),
	DM_Rule (125, 3, "EYA", 1),
	DM_Rule (126, 3, "EYE", 1),
	DM_Rule (127, 3, "EYI", 1),
	DM_Rule (128, 3, "EYO", 1),
	DM_Rule (129, 3, "EYU", 1),
	DM_Rule (130, 3, "EYY", 1),
	DM_Rule (131, 3, "OIA", 1),
	DM_Rule (132, 3, "OIE", 1),
	DM_Rule (133, 3, "OII", 1),
	DM_Rule (134, 3, "OIO", 1),
	DM_Rule (135, 3, "OIU", 1),
	DM_Rule (136, 3, "OIY", 1),
	DM_Rule (137, 3, "SCH", 4),
	DM_Rule (138, 3, "TCH", 4),
	DM_Rule (139, 3, "TRS", 4),
	DM_Rule (140, 3, "TRZ", 4),
	DM_Rule (141, 3, "TSH", 4),
	DM_Rule (142, 3, "TTS", 4),
	DM_Rule (143, 3, "TTZ", 4),
	DM_Rule (144, 3, "TSZ", 4),
	DM_Rule (145, 3, "TZS", 4),
	DM_Rule (146, 3, "UIA", 1),
	DM_Rule (147, 3, "UIE", 1),
	DM_Rule (148, 3, "UII", 1),
	DM_Rule (149, 3, "UIO", 1),
	DM_Rule (150, 3, "UIU", 1),
	DM_Rule (151, 3, "UIY", 1),
	DM_Rule (152, 3, "UJA", 1),
	DM_Rule (153, 3, "UJE", 1),
	DM_Rule (154, 3, "UJI", 1),
	DM_Rule (155, 3, "UJO", 1),
	DM_Rule (156, 3, "UJU", 1),
	DM_Rule (157, 3, "UJY", 1),
	DM_Rule (158, 3, "UYA", 1),
	DM_Rule (159, 3, "UYE", 1),
	DM_Rule (160, 3, "UYI", 1),
	DM_Rule (161, 3, "UYO", 1),
	DM_Rule (162, 3, "UYU", 1),
	DM_Rule (163, 3, "UYY", 1),
	DM_Rule (164, 3, "ZSH", 4),
	DM_Rule (165, 4, "TSCH", 4),
	DM_Rule (166, 4, "TTCH", 4),
	DM_Rule (167, 4, "TTSZ", 4),
	DM_Rule (168, 4, "ZSCH", 4),
	DM_Rule (169, 5, "TTSCH", 4)
};

// Beginning

DM_Rule_Bounds DM_Soundex::DM_Rule_Beginning_Bounds[7] = {
	DM_Rule_Bounds(0, 25),
	DM_Rule_Bounds(26, 78),
	DM_Rule_Bounds(79, 175),
	DM_Rule_Bounds(176, 188),
	DM_Rule_Bounds(189, 193),
	DM_Rule_Bounds(194, 195),
	DM_Rule_Bounds(196, 196)
};

DM_Rule DM_Soundex::DM_Rule_Beginning[197] = {
	DM_Rule (0, 1, "A", 0),
	DM_Rule (1, 1, "B", 7),
	DM_Rule (2, 1, "C", 5, 4),
	DM_Rule (3, 1, "D", 3),
	DM_Rule (4, 1, "E", 0),
	DM_Rule (5, 1, "F", 7),
	DM_Rule (6, 1, "G", 5),
	DM_Rule (7, 1, "H", 5),
	DM_Rule (8, 1, "I", 0),
	DM_Rule (9, 1, "J", 1, 4),
	DM_Rule (10, 1, "K", 5),
	DM_Rule (11, 1, "L", 8),
	DM_Rule (12, 1, "M", 6),
	DM_Rule (13, 1, "N", 6),
	DM_Rule (14, 1, "O", 0),
	DM_Rule (15, 1, "P", 7),
	DM_Rule (16, 1, "Q", 5),
	DM_Rule (17, 1, "R", 9),
	DM_Rule (18, 1, "S", 4),
	DM_Rule (19, 1, "T", 3),
	DM_Rule (20, 1, "U", 0),
	DM_Rule (21, 1, "V", 7),
	DM_Rule (22, 1, "W", 7),
	DM_Rule (23, 1, "X", 5),
	DM_Rule (24, 1, "Y", 1),
	DM_Rule (25, 1, "Z", 4),
	DM_Rule (26, 2, "AI", 0),
	DM_Rule (27, 2, "AJ", 0),
	DM_Rule (28, 2, "AU", 0),
	DM_Rule (29, 2, "AY", 0),
	DM_Rule (30, 2, "CH", 5, 4),
	DM_Rule (31, 2, "CK", 5, 45),
	DM_Rule (32, 2, "CS", 4),
	DM_Rule (33, 2, "CZ", 4),
	DM_Rule (34, 2, "DS", 4),
	DM_Rule (35, 2, "DT", 3),
	DM_Rule (36, 2, "DZ", 4),
	DM_Rule (37, 2, "EI", 0),
	DM_Rule (38, 2, "EJ", 0),
	DM_Rule (39, 2, "EU", 1),
	DM_Rule (40, 2, "EY", 0),
	DM_Rule (41, 2, "FB", 7),
	DM_Rule (42, 2, "HA", 5),
	DM_Rule (43, 2, "HE", 5),
	DM_Rule (44, 2, "HI", 5),
	DM_Rule (45, 2, "HO", 5),
	DM_Rule (46, 2, "HU", 5),
	DM_Rule (47, 2, "HY", 5),
	DM_Rule (48, 2, "IA", 1),
	DM_Rule (49, 2, "IE", 1),
	DM_Rule (50, 2, "IO", 1),
	DM_Rule (51, 2, "IU", 1),
	DM_Rule (52, 2, "KH", 5),
	DM_Rule (53, 2, "KS", 5),
	DM_Rule (54, 2, "MN", 66),
	DM_Rule (55, 2, "NM", 66),
	DM_Rule (56, 2, "OI", 0),
	DM_Rule (57, 2, "OJ", 0),
	DM_Rule (58, 2, "OY", 0),
	DM_Rule (59, 2, "PF", 7),
	DM_Rule (60, 2, "PH", 7),
	DM_Rule (61, 2, "RS", 94, 4),
	DM_Rule (62, 2, "RZ", 94, 4),
	DM_Rule (63, 2, "SC", 2),
	DM_Rule (64, 2, "SD", 2),
	DM_Rule (65, 2, "SH", 4),
	DM_Rule (66, 2, "ST", 43),
	DM_Rule (67, 2, "SZ", 4),
	DM_Rule (68, 2, "TC", 4),
	DM_Rule (69, 2, "TH", 3),
	DM_Rule (70, 2, "TS", 4),
	DM_Rule (71, 2, "TZ", 4),
	DM_Rule (72, 2, "UE", 0),
	DM_Rule (73, 2, "UI", 0),
	DM_Rule (74, 2, "UJ", 0),
	DM_Rule (75, 2, "UY", 0),
	DM_Rule (76, 2, "ZD", 2),
	DM_Rule (77, 2, "ZH", 4),
	DM_Rule (78, 2, "ZS", 4),
	DM_Rule (79, 3, "AIA", 1),
	DM_Rule (80, 3, "AIE", 1),
	DM_Rule (81, 3, "AII", 1),
	DM_Rule (82, 3, "AIO", 1),
	DM_Rule (83, 3, "AIU", 1),
	DM_Rule (84, 3, "AIY", 1),
	DM_Rule (85, 3, "AJA", 1),
	DM_Rule (86, 3, "AJE", 1),
	DM_Rule (87, 3, "AJI", 1),
	DM_Rule (88, 3, "AJO", 1),
	DM_Rule (89, 3, "AJU", 1),
	DM_Rule (90, 3, "AJY", 1),
	DM_Rule (91, 3, "AUA", 1),
	DM_Rule (92, 3, "AUE", 1),
	DM_Rule (93, 3, "AUI", 1),
	DM_Rule (94, 3, "AUO", 1),
	DM_Rule (95, 3, "AUU", 1),
	DM_Rule (96, 3, "AUY", 1),
	DM_Rule (97, 3, "AYA", 1),
	DM_Rule (98, 3, "AYE", 1),
	DM_Rule (99, 3, "AYI", 1),
	DM_Rule (100, 3, "AYO", 1),
	DM_Rule (101, 3, "AYU", 1),
	DM_Rule (102, 3, "AYY", 1),
	DM_Rule (103, 3, "CHS", 5),
	DM_Rule (104, 3, "CSZ", 4),
	DM_Rule (105, 3, "CZS", 4),
	DM_Rule (106, 3, "DRS", 4),
	DM_Rule (107, 3, "DRZ", 4),
	DM_Rule (108, 3, "DSH", 4),
	DM_Rule (109, 3, "DSZ", 4),
	DM_Rule (110, 3, "DZH", 4),
	DM_Rule (111, 3, "DZS", 4),
	DM_Rule (112, 3, "EIA", 1),
	DM_Rule (113, 3, "EIE", 1),
	DM_Rule (114, 3, "EII", 1),
	DM_Rule (115, 3, "EIO", 1),
	DM_Rule (116, 3, "EIU", 1),
	DM_Rule (117, 3, "EIY", 1),
	DM_Rule (118, 3, "EJA", 1),
	DM_Rule (119, 3, "EJE", 1),
	DM_Rule (120, 3, "EJI", 1),
	DM_Rule (121, 3, "EJO", 1),
	DM_Rule (122, 3, "EJU", 1),
	DM_Rule (123, 3, "EJY", 1),
	DM_Rule (124, 3, "EUA", 1),
	DM_Rule (125, 3, "EUE", 1),
	DM_Rule (126, 3, "EUI", 1),
	DM_Rule (127, 3, "EUO", 1),
	DM_Rule (128, 3, "EUU", 1),
	DM_Rule (129, 3, "EUY", 1),
	DM_Rule (130, 3, "EYA", 1),
	DM_Rule (131, 3, "EYE", 1),
	DM_Rule (132, 3, "EYI", 1),
	DM_Rule (133, 3, "EYO", 1),
	DM_Rule (134, 3, "EYU", 1),
	DM_Rule (135, 3, "EYY", 1),
	DM_Rule (136, 3, "OIA", 1),
	DM_Rule (137, 3, "OIE", 1),
	DM_Rule (138, 3, "OII", 1),
	DM_Rule (139, 3, "OIO", 1),
	DM_Rule (140, 3, "OIU", 1),
	DM_Rule (141, 3, "OIY", 1),
	DM_Rule (142, 3, "SCH", 4),
	DM_Rule (143, 3, "SHD", 2),
	DM_Rule (144, 3, "SHT", 2),
	DM_Rule (145, 3, "SZD", 2),
	DM_Rule (146, 3, "SZT", 2),
	DM_Rule (147, 3, "TCH", 4),
	DM_Rule (148, 3, "TRS", 4),
	DM_Rule (149, 3, "TRZ", 4),
	DM_Rule (150, 3, "TSH", 4),
	DM_Rule (151, 3, "TTS", 4),
	DM_Rule (152, 3, "TTZ", 4),
	DM_Rule (153, 3, "TSZ", 4),
	DM_Rule (154, 3, "TZS", 4),
	DM_Rule (155, 3, "UIA", 1),
	DM_Rule (156, 3, "UIE", 1),
	DM_Rule (157, 3, "UII", 1),
	DM_Rule (158, 3, "UIO", 1),
	DM_Rule (159, 3, "UIU", 1),
	DM_Rule (160, 3, "UIY", 1),
	DM_Rule (161, 3, "UJA", 1),
	DM_Rule (162, 3, "UJE", 1),
	DM_Rule (163, 3, "UJI", 1),
	DM_Rule (164, 3, "UJO", 1),
	DM_Rule (165, 3, "UJU", 1),
	DM_Rule (166, 3, "UJY", 1),
	DM_Rule (167, 3, "UYA", 1),
	DM_Rule (168, 3, "UYE", 1),
	DM_Rule (169, 3, "UYI", 1),
	DM_Rule (170, 3, "UYO", 1),
	DM_Rule (171, 3, "UYU", 1),
	DM_Rule (172, 3, "UYY", 1),
	DM_Rule (173, 3, "ZDZ", 2),
	DM_Rule (174, 3, "ZHD", 2),
	DM_Rule (175, 3, "ZSH", 4),
	DM_Rule (176, 4, "SCHD", 2),
	DM_Rule (177, 4, "SCHT", 2),
	DM_Rule (178, 4, "SHCH", 2),
	DM_Rule (179, 4, "STCH", 2),
	DM_Rule (180, 4, "STRS", 2),
	DM_Rule (181, 4, "STRZ", 2),
	DM_Rule (182, 4, "STSH", 2),
	DM_Rule (183, 4, "SZCS", 2),
	DM_Rule (184, 4, "SZCZ", 2),
	DM_Rule (185, 4, "TTCH", 4),
	DM_Rule (186, 4, "TTSZ", 4),
	DM_Rule (187, 4, "ZDZH", 2),
	DM_Rule (188, 4, "ZSCH", 4),
	DM_Rule (189, 5, "SHTCH", 2),
	DM_Rule (190, 5, "SHTSH", 2),
	DM_Rule (191, 5, "STSCH", 2),
	DM_Rule (192, 5, "TTSCH", 4),
	DM_Rule (193, 5, "ZHDZH", 2),
	DM_Rule (194, 6, "SCHTCH", 2),
	DM_Rule (195, 6, "SCHTSH", 2),
	DM_Rule (196, 7, "SCHTSCH", 2)
};

// Ending

DM_Rule_Bounds DM_Soundex::DM_Rule_Ending_Bounds[7] = {
	DM_Rule_Bounds (0, 7),
	DM_Rule_Bounds (8, 30),
	DM_Rule_Bounds (31, 37),
	DM_Rule_Bounds (38, 47),
	DM_Rule_Bounds (48, 51),
	DM_Rule_Bounds (52, 53),
	DM_Rule_Bounds (54, 54)
};

DM_Rule DM_Soundex::DM_Rule_Ending[55] = {
	DM_Rule (0, 1, "A", 0),
	DM_Rule (1, 1, "E", 0),
	DM_Rule (2, 1, "H", 0),
	DM_Rule (3, 1, "I", 0),
	DM_Rule (4, 1, "O", 0),
	DM_Rule (5, 1, "U", 0),
	DM_Rule (6, 1, "X", 54),
	DM_Rule (7, 1, "Y", 0),
	DM_Rule (8, 2, "AI", 0),
	DM_Rule (9, 2, "AJ", 0),
	DM_Rule (10, 2, "AU", 0),
	DM_Rule (11, 2, "AY", 0),
	DM_Rule (12, 2, "EI", 0),
	DM_Rule (13, 2, "EJ", 0),
	DM_Rule (14, 2, "EU", 0),
	DM_Rule (15, 2, "EY", 0),
	DM_Rule (16, 2, "IA", 0),
	DM_Rule (17, 2, "IE", 0),
	DM_Rule (18, 2, "IO", 0),
	DM_Rule (19, 2, "IU", 0),
	DM_Rule (20, 2, "KS", 54),
	DM_Rule (21, 2, "OI", 0),
	DM_Rule (22, 2, "OJ", 0),
	DM_Rule (23, 2, "OY", 0),
	DM_Rule (24, 2, "SC", 3),
	DM_Rule (25, 2, "SD", 43),
	DM_Rule (26, 2, "UE", 0),
	DM_Rule (27, 2, "UI", 0),
	DM_Rule (28, 2, "UJ", 0),
	DM_Rule (29, 2, "UY", 0),
	DM_Rule (30, 2, "ZD", 43),
	DM_Rule (31, 3, "CHS", 5),
	DM_Rule (32, 3, "SHT", 4),
	DM_Rule (33, 3, "SZT", 43),
	DM_Rule (34, 3, "SHD", 43),
	DM_Rule (35, 3, "SZD", 43),
	DM_Rule (36, 3, "ZDZ", 4),
	DM_Rule (37, 3, "ZHD", 43),
	DM_Rule (38, 4, "SHCH", 4),
	DM_Rule (39, 4, "SCHD", 4),
	DM_Rule (40, 4, "STCH", 3),
	DM_Rule (41, 4, "SCHT", 4),
	DM_Rule (42, 4, "STRZ", 4),
	DM_Rule (43, 4, "STRS", 4),
	DM_Rule (44, 4, "STSH", 4),
	DM_Rule (45, 4, "SZCZ", 4),
	DM_Rule (46, 4, "SZCS", 4),
	DM_Rule (47, 4, "ZDZH", 4),
	DM_Rule (48, 5, "SHTCH", 4),
	DM_Rule (49, 5, "SHTSH", 4),
	DM_Rule (50, 5, "STSCH", 3),
	DM_Rule (51, 5, "ZHDZH", 4),
	DM_Rule (52, 6, "SCHTSH", 43),
	DM_Rule (53, 6, "SCHTCH", 43),
	DM_Rule (54, 7, "SCHTSCH", 43)
};